import java.util.*;

//1700. 无法吃午餐的学生数量
class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        Queue<Integer> q = new LinkedList<>();//学生
        Stack<Integer> s = new Stack<>();//三明治
        int flag=0;
        for(int k:students){
            q.offer(k);
        }
        for(int i=sandwiches.length-1;i>=0;i--){
            s.add(sandwiches[i]);
        }
        while(!q.isEmpty()&&flag!=q.size()){
            if(q.peek()==s.peek()){
                q.poll();
                s.pop();
                flag=0;
            }
            while(!q.isEmpty()&&q.peek()!=s.peek()&&flag!=q.size()){
                int temp=q.poll();
                q.offer(temp);
                flag++;
            }
        }
        return q.size();

    }
}



//146. LRU 缓存
class LRUCache {
    private int capacity;
    private LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // LinkedHashMap，按访问顺序排列
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true);
    }
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        cache.put(key, value);
        // 超过容量时移除最老的元素
        if (cache.size() > capacity) {
            Integer oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
    }
}

//方法2:链表+哈希表
class LRUCache2 {
    class DlinkedNode {
        int key;
        int value;
        DlinkedNode prev;
        DlinkedNode next;
    }

    private Map<Integer, DlinkedNode> map;
    private int size;
    private int capacity;
    private DlinkedNode head, tail; // 头尾结点并不用于真的结点,用来辅助删除增加结点，也就是伪头节点和伪尾节点，作为哨兵结点

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        map = new HashMap<>();
        tail = new DlinkedNode();// 这里注意初始化头尾结点，并且让他们相互指向
        head = new DlinkedNode();
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        DlinkedNode node = map.get(key);
        if(node==null){
            return -1;
        }
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DlinkedNode node = map.get(key);
        if (node == null) { // 为空说明没这个节点，那么就添加进去
            DlinkedNode newNode = new DlinkedNode(); // 创建一个新节点
            newNode.key = key;
            newNode.value = value;
            map.put(key, newNode); // 放进哈希表
            addToHead(newNode); // 并且放到链表的头结点
            size++;
            if (size > capacity) { // 大于容量就移出最久没使用的节点
                DlinkedNode Dnode = removeTail();
                map.remove(Dnode.key); // 记得更新一下哈希表
                size--;
            }
        } else { // 存在该节点就该一下value即可
            node.value = value;
            removeNode(node); // 记得也更新一下头结点，把该节点放到头结点
            addToHead(node);
            return;
        }
    }

    public void addToHead(DlinkedNode node) { // 放到头节点
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }

    public void removeNode(DlinkedNode node) { // 移除结点,gc回收
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public  DlinkedNode removeTail() { // 移除尾结点
        DlinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
